package main.Q601_700;

import java.util.*;

public class Q651_660 {
    public static void main(String[] args) {
        System.out.println("Question651：");
        System.out.println("Question652：");
        System.out.println("Question653：两数之和Ⅳ-输入二叉搜索数");
        System.out.println("Question654：最大二叉树");
        System.out.println("Question655：");
        System.out.println("Question656：");
        System.out.println("Question657：机器人能否返回原点");
        System.out.println("Question658：找到K个最接近的元素");
        System.out.println("Question659：");
        System.out.println("Question660：");
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
      this.val = val;
      this.left = left;
      this.right = right;
    }
}

class Question653{
    public boolean findTarget(TreeNode root, int k) {
        Set<Integer> set=new HashSet<>();
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            TreeNode curNode=queue.poll();
            if (set.contains(k-curNode.val)) return true;//存在两数和为目标结果
            set.add(curNode.val);//当前节点值加入set中
            if (curNode.left!=null) queue.add(curNode.left);
            if (curNode.right!=null) queue.add(curNode.right);
        }
        return false;
    }
}

class Question654{
    public int getMaxIndex(int[] nums,int left,int right){//获取该段数组最大值的下标
        int index=left;
        while (left<=right){
            if (nums[left]>nums[index]) index=left;
            left++;
        }
        return index;
    }
    public TreeNode process(int[] nums,int left,int right){
        if (left>right||right<left) return null;//不存在数据，无节点
        int index=getMaxIndex(nums,left,right);//获取当前段数组最大值下标
        TreeNode curNode=new TreeNode(nums[index]);//构建本节点
        curNode.left=process(nums,left,index-1);//构建左子树节点
        curNode.right=process(nums,index+1,right);//构建右子树节点
        return curNode;
    }
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        if (nums.length==0) return null;
        int left=0,right= nums.length-1;
        TreeNode root=process(nums,left,right);
        return root;
    }
}

class Question657{
    public boolean judgeCircle(String moves) {
        int i=0,j=0;
        char[] strs=moves.toCharArray();
        for (char c:strs){
            switch (c){
                case 'R':j++;break;
                case 'L':j--;break;
                case 'U':i--;break;
                case 'D':i++;break;
            }
        }
        if (i==0&&j==0) return true;
        else return false;
    }
}

class Question658{
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        List<Integer> list=new ArrayList<>();
        int left=0,right= arr.length-1,index=-1;
        boolean flag=false;
        while (left<right){//寻找道最接近的元素
            int mid=left+(right-left)/2;
            if (arr[mid]==x) {
                index=mid;
                break;
            }else if (arr[mid]>x){
                if (mid-1>left) right=mid;
                else if (mid==left+1){
                    right=mid;
                    flag=true;
                }else if (mid==left) flag=true;
            }else {
                if (mid+1<right) left=mid;
                else if (mid==right-1) {
                    left=mid;
                    flag=true;
                }else if (mid==left) flag=true;
            }
            if (flag) break;
        }
        if (arr[0]>=x) index=0;
        if (arr[arr.length-1]<=x) index= arr.length-1;
        if (index==-1) {
            index= Math.abs(arr[left]-x)>Math.abs(arr[right]-x) ? right : left;
        }
        list.add(arr[index]);
        left=index-1;
        right=index+1;
        while (list.size()<k){
            if (left<0) {
                list.add(arr[right]);
                right++;
            }else if (right>= arr.length){
                list.add(arr[left]);
                left--;
            }else {
                if (Math.abs(arr[left]-x)>Math.abs(arr[right]-x)) {
                    list.add(arr[right]);
                    right++;
                }else {
                    list.add(arr[left]);
                    left--;
                }
            }
        }
        Collections.sort(list);
        return list;
    }
}